package exercises.leetcode;

/**
 * <a href="https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/">
 * 剑指 Offer 53 - I. 在排序数组中查找数字 I</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 统计一个数字在排序数组中出现的次数。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * <p>
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: 0
 *  
 * <p>
 * 提示：
 * <p>
 * 0 <= nums.length <= 105
 * -109 <= nums[i] <= 109
 * nums 是一个非递减数组
 * -109 <= target <= 109
 *  
 * <p>
 * 注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 *
 * @author or2
 * @date 2021年09月22日 时间: 17:29
 */
public class Offer53 {
    public int search(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }

        /*搜索区间 [rightIndex, leftIndex)*/
        int rightIndex = nums.length;
        int leftIndex = 0;
        int midIndex = 0;
        while (leftIndex < rightIndex) {
            midIndex = leftIndex + (rightIndex - leftIndex >> 1);
            if (nums[midIndex] == target) {
                break;
            }
            if (nums[midIndex] > target) {
                rightIndex = midIndex;
            } else {
                leftIndex = midIndex + 1;
            }
        }

        if (nums[midIndex] != target) {
            return 0;
        }

        /*查找两边*/
        int times = 1;
        if (nums[0] == target) {
            times += midIndex;
        }else {
            leftIndex = midIndex - 1;
            while (nums[leftIndex--] == target) times++;
        }
        if (nums[nums.length - 1] == target) {
            times += nums.length - midIndex - 1;
        }else {
            rightIndex = midIndex + 1;
            while (nums[rightIndex++] == target) times++;
        }

        return times;
    }
}
